#include <iostream>
#include <queue>
#include <vector>
using namespace std;

/**
 * @方法: dp
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
 */
int dp[302][302];
int maximalSquare(vector<vector<char>>& matrix) {
    for (int i = 0; i < matrix[0].size(); i++)
        if (matrix[0][i] == '0')
            dp[0][i] = 0;
        else
            dp[0][i] = 1;

    for (int i = 0; i < matrix.size(); i++)
        if (matrix[i][0] == '0')
            dp[i][0] = 0;
        else
            dp[i][0] = 1;

    for (int row = 1; row < matrix.size(); row++) {
        for (int col = 1; col < matrix[0].size(); col++) {
            if (matrix[row][col] == '0')
                dp[row][col] = 0;
            else if (dp[row][col - 1] == dp[row - 1][col]) {
                int side = dp[row][col - 1];
                if (matrix[row - side][col - side] == '1') {
                    dp[row][col] = side + 1;
                } else {
                    dp[row][col] = side;
                }
            } else if (dp[row][col - 1] != dp[row - 1][col]) {
                dp[row][col] = min(dp[row - 1][col], dp[row][col - 1]) + 1;
            }
        }
    }
    int ans = 0;
    for (int row = 0; row < matrix.size(); row++) {
        for (int col = 0; col < matrix[0].size(); col++) {
            ans = max(ans, dp[row][col]);
        }
    }
    return ans * ans;
}


/**
 * @方法: 暴力
 * @时间复杂度: o(m * n * min(m,n)^2)
 * @空间复杂度: o()
 * @评价: 对每个左上角，层次遍历
 */
struct node {
    int row;
    int col;
};

int getSquare(int row, int col, vector<vector<char>>& matrix) {
    int ans = 1;
    queue<node> Q;
    Q.push(node{row, col});
    while (!Q.empty()) {
        int size = Q.size();
        for (int i = 0; i < size; i++) {
            int r = Q.front().row;
            int c = Q.front().col;
            Q.pop();
            if (i < (size - 1) / 2) {
                if (r + 1 == matrix.size() || matrix[r + 1][c] != '1')
                    return ans;
                else
                    Q.push(node{r + 1, c});
            } else if (i == (size - 1) / 2) {
                if (r + 1 == matrix.size() || c + 1 == matrix[0].size() ||
                    matrix[r + 1][c] != '1' || matrix[r][c + 1] != '1' ||
                    matrix[r + 1][c + 1] != '1')
                    return ans;
                else {
                    Q.push(node{r + 1, c});
                    Q.push(node{r + 1, c + 1});
                    Q.push(node{r, c + 1});
                }
            } else if (i > (size - 1) / 2) {
                if (c + 1 == matrix[0].size() || matrix[r][c + 1] != '1')
                    return ans;
                else
                    Q.push(node{r, c + 1});
            }
        }
        ans++;
    }
    return ans;
}

int maximalSquare(vector<vector<char>>& matrix) {
    int ans = 0;
    for (int row = 0; row < matrix.size(); row++) {
        for (int col = 0; col < matrix[0].size(); col++) {
            if (matrix[row][col] == '0') continue;
            if (matrix[0].size() - col <= ans) continue;
            if (matrix.size() - row <= ans) continue;
            ans = max(ans, getSquare(row, col, matrix));
        }
    }
    return ans * ans;
}